<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    function Btree() {
      //定义二叉树的结点
      function Node(key) {
        this.key = key
        this.left = null
        this.right = null
      }
      this.root = null
      //二叉树的插入函数
      this.insert = function (key) {
        let newNode = new Node(key)
        if (this.root === null) {
          this.root = newNode
        } else (
          this.insertNode(this.root, newNode)
        )
      }
      //二叉树插入节点的辅助函数
      this.insertNode = function (preNode, newNode) {
        let preKey = preNode.key
        let newKey = newNode.key
        if (newKey < preKey) {
          if (preNode.left === null) {
            preNode.left = newNode
          } else {
            this.insertNode(preNode.left, newNode)
          }
        }
        if (newKey > preKey) {
          if (preNode.right === null) {
            preNode.right = newNode
          } else (
            this.insertNode(preNode.right, newNode)
          )
        }
      }
      //二叉树的查找
      this.find = function (key) {
        let current = this.root
        while (current) {
          if (current.key === key) {
            return current
          } else if (current.key > key) {
            current = current.left
          } else {
            current = current.right
          }
        }
        return null
      }
      //二叉树的先序遍历 另外其他两种的遍历也是类似实现方式
      let arr = []
      this.preOrder = function (Node) {
        if (Node) {
          arr.push(Node.key)
          this.preOrder(Node.left)
          this.preOrder(Node.right)
        }
        return arr
      }
      //二叉树的翻转 交换每个节点的左右子树即可
      this.changeTree = function (Node) {
        if (Node) {
          var tempNode = Node.left
          Node.left = Node.right
          Node.right = tempNode
          this.changeTree(Node.left)
          this.changeTree(Node.right)
        }
        return Node
      }
      //二叉树的删除 分三种情况 

      //一是删除叶子节点 算法：将叶子节点赋值为空 返回即可
      //二是删除的节点只有左节点或者只有右节点 算法：将左节点或者右节点赋值给待删除节点 返回即可
      //三是删除的节点有左节点又有右节点 算法：找到待删除结点的右节点中的最小结点 将该结点的值代替待删除结点 然后将最小结点置空即可
      //不管是哪种情况 只要满足删除后还遵循二叉查找树的规则即可
      this.removeNode = function (Node, key) {
        if (Node === null) {
          return null
        }
        if (Node.key > key) {
          Node.left = this.removeNode(Node.left, key)
          return Node
        }
        else if (Node.key < key) {
          Node.right = this.removeNode(Node.right, key)
          return Node
        } else {
          //第一种情况
          if (Node.right === null && Node.right === null) {
            Node = null
            return Node
          }
          //第二种情况
          if (Node.left === null) {
            Node = Node.right
            return Node
          } else if (Node.right === null) {
            Node = Node.left
            return Node
          }
          //第三种情况
          var minNode = this.findMinNode(Node.right)
          Node.key = minNode.key
          minNode = this.removeNode(Node.right, minNode.key)
          return Node

        }
      }
      //第三种结点删除的辅助函数 用来找出最小右节点
      this.findMinNode = function (Node) {
        if (Node === null) {
          return null
        }
        if (Node.left) {
          return this.findMinNode(Node.left)
        } else {
          return Node
        }
      }

    }

    var tree = new Btree()
    var arr = [5, 8, 3, 6, 1, 2]
    arr.map(v => { tree.insert(v) })
  </script>
</body>

</html>